package style.zcyLeetCode.a_0005_二叉树;

/**
 * 判断是否平衡二叉树
 * 左右子树高度小于2
 */
public class IsBalancedTree {

    // 贴吧
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data){
            this.value = data;
        }
    }

    private static boolean isBalanced = false; // 最后的返回值

    public static boolean IsBalanced_Solution( Node root) {
        getDepth(root);
        return isBalanced;
    }

    public static int getDepth(Node root) {
        if (root == null) {
            isBalanced = true;
            return 0;
        }
        int left = getDepth(root.left);
        int right = getDepth(root.right);
        int depth = (left > right ? left : right) + 1;
        if (Math.abs(left - right) <= 1) {
            isBalanced = true;
        } else {
            isBalanced = false;
        }
        return depth;  //下层的深度，上层可以接着用免得再遍历
    }

    public static void main(String[] args) {
        Node node = new Node(6);
        node.left = new Node(5);
        node.right = new Node(7);
        node.left.left = new Node(4);
        node.left.right = new Node(3);
        node.right.left = new Node(8);
        node.right.right = new Node(9);
//        node.right.right.right = new Node(9);
//        node.right.right.right.right = new Node(9);
//        node.right.right.right.right.right = new Node(9);
//        node.right.right.right.right.right.right = new Node(9);

//        System.out.println(isBalanced(node));
        System.out.println(IsBalanced_Solution(node));
    }
}
